package homework2;

import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    TreeNode node0;
    TreeNode node1;
    TreeNode node2;
    TreeNode node3;
    TreeNode node4;
    TreeNode node5;
    TreeNode node6;
    TreeNode node7;
    TreeNode node8;
    public TreeNode createTree(){
        node3 = new TreeNode(3);
        node5 = new TreeNode(5);
        node1 = new TreeNode(1);
        node6 = new TreeNode(6);
        node2 = new TreeNode(2);
        node0 = new TreeNode(0);
        node8 = new TreeNode(8);
        node7 = new TreeNode(7);
        node4 = new TreeNode(4);

        node3.left = node5;
        node3.right = node1;
        node5.left = node6;
        node5.right = node2;
        node1.left = node0;
        node1.right = node8;
        node2.left = node7;
        node2.left = node4;

        return node3;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null){
            return null;
        }
        Stack<TreeNode> stackP = getPath(root, p);
        Stack<TreeNode> stackQ = getPath(root, q);
        int step = stackP.size() - stackQ.size();
        while(step != 0){
            if(step > 0){
                stackP.pop();
                step--;
            }else{
                stackQ.pop();
                step++;
            }
        }
        //stackP和stackQ拥有相同多的元素
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            if(stackP.peek() == stackQ.peek()){
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;
    }
    private Stack<TreeNode> getPath(TreeNode root, TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        if(root == null || node == null){
            return stack;
        }
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.peek();
            if(top == node){
                return stack;
            }else if(top.right == null || top.right == prev){
                prev = stack.pop();
            }else{
                cur = top.right;
            }
        }
        return stack;
    }

    private int sum;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                sum += cur.val;
                cur = cur.left;
            }
            top = stack.peek();
            //判断叶子结点
            if(top.left == null && top.right == null){
                if(sum == targetSum){
                    return true;
                }else{
                    prev = stack.pop();
                    sum -= prev.val;
                }
            }else{
                if(top.right == prev || top.left == prev){
                    prev = stack.pop();
                    sum -= prev.val;
                }else{
                    cur = top.right;
                }
            }
        }
        return false;
    }

    public TreeNode createTree2(){
        node1 = new TreeNode(1);
        node2 = new TreeNode(2);
        node1.left = node2;
        return node1;
    }
}
